package a09_贪心算法;

import java.util.Arrays;

/**
 * <p>
 * a18_无重叠区间复习3
 * </p>
 *
 * @author flyduck
 * @since 2025/4/24
 */
public class a18_无重叠区间复习3 {

    public static void main(String[] args) {
        a18_无重叠区间复习3 a18_无重叠区间复习3 = new a18_无重叠区间复习3();
        System.out.println(a18_无重叠区间复习3.eraseOverlapIntervals(new int[][]{{1, 4}, {2, 6}, {3, 7}}));
    }

    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (interval1,interval2) -> {
            if(interval1[0] == interval2[0]){
                return interval1[1] > interval2[1] ? 1 : -1;
            }else {
                return interval1[0] > interval2[0] ? 1 : -1;
            }
        });


        int result = 0;
        for (int i = 1; i < intervals.length; i++) {
            if(intervals[i][0] < intervals[i-1][1]){//重叠了，需要移除
                result++;
                intervals[i][1] = Math.min(intervals[i-1][1], intervals[i][1]);
            }
        }

        return result;


    }
}
